public class Sort {
    public static void quickSort(int[] array){
        quickSort(array,0,array.length-1);
    }
    public static void quickSort(int[] array,int start,int end){
     if(start>=end) return ;
     int middle = partition(array,start,end);
     quickSort(array,start,middle-1);
     quickSort(array,middle+1,end);
    }
    private static int partition(int[] array,int start,int end){
      int left = start+1;
      int pivot = array[start];
      int right = end;
      while(left<right){
          while(left<right && array[left]<=pivot){
              left++;
          }
          if(left!=right){
              swap(array,left,right);
              right--;
          }
      }
      if(left==right && array[right]>pivot){
          right--;
      }
      if(right!=start){
          swap(array,start,right);
      }
      return right;
    }
    private static void swap(int[] array,int x,int y){
        int tem = array[x];
        array[x] = array[y];
        array[y] = tem;
    }
}
